package q654_constructMaximumBinaryTree;

import CommonClass.TreeNode;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class Solution_3 {
    /*
    单调栈的方式
     */
    public static void main(String[] args) {
        int[] nums = {3, 2, 1, 6, 0, 5};
        int n = nums.length;
        int[] left = new int[n];
        int[] right = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();
        Arrays.fill(left, -1);
        Arrays.fill(right, -1);
        TreeNode[] tree = new TreeNode[n];
        for (int i = 0; i < n; ++i) {
            tree[i] = new TreeNode(nums[i]);
            while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
                right[stack.pop()] = i;
            }
            if (!stack.isEmpty()) {
                left[i] = stack.peek();
            }
            stack.push(i);
        }
        System.out.println(Arrays.toString(nums));

        System.out.println("left:");
        System.out.println(Arrays.toString(left));

        System.out.println("right:");
        System.out.println(Arrays.toString(right));
    }

    /*
    单调栈的复合使用
     */
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        int n = nums.length;
        Deque<Integer> stack = new ArrayDeque<>();
        int[] left = new int[n];
        int[] right = new int[n];
        Arrays.fill(left, -1);
        Arrays.fill(right, -1);
        TreeNode[] tree = new TreeNode[n];
        for (int i = 0; i < n; ++i) {
            // 顺便把tree数组建好
            tree[i] = new TreeNode(nums[i]);
            // 找出每一个元素左侧和右侧第一个比它大的元素所在的位置
            // 这个单调栈的方法 在一次循环能够同时找出一个元素左侧和右侧第一个大于它的元素位置
            while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
                right[stack.pop()] = i;
            }
            if (!stack.isEmpty()) {
                left[i] = stack.peek();
            }
            stack.push(i);
        }

        TreeNode root = null;
        for (int i = 0; i < n; ++i) {
            if (left[i] == -1 && right[i] == -1) {
                root = tree[i];

                // 如果左侧的元素较小，那么该元素就是左侧元素的右子节点；
                // 如果右侧的元素较小，那么该元素就是右侧元素的左子节点。
            } else if (right[i] == -1 || (left[i] != -1 && nums[left[i]] < nums[right[i]])) {
                tree[left[i]].right = tree[i];
            } else {
                tree[right[i]].left = tree[i];
            }
        }
        return root;
    }
}
